package ljl.codetop300.test;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;

/**
 * 思路：形成一个列表：from: [to]，这个 to 是依赖列表还是被依赖列表？
 * 答案：试，一共两种情况，为何不试试？
 *
 * 假设是 被依赖：【依赖者1，依赖者2...】，dfs 是从第一个开始，找依赖它的
 * 找到某个课程依赖者是空的，我们就可以先学它，所以可行
 *
 * 错误想法：
 * 假设是 依赖者：【被依赖1，被依赖2...】，dfs 从依赖者开始找，啥也找不到吧
 * 最后找到的是被依赖的某一个，它啥也不是，只知道它被依赖了，我什么也做不了；
 * 错！最后一个依赖者，的被依赖是空的，说明啥，说明它谁也不依赖，所以，它是第一个！
 * 所以我的结论是正着反着都可以
 * 错！这样很容易就走到最后了，把一个应该处于中间的节点提前输出出来了：某个节点依赖的很少，但是依赖它的很多，它不能往前放
 * 我感觉硬要做也能做，但是比较麻烦，还是倒着简单
 *
 */
public class topology_sort_tests {

  /**
   * 1. 一个图，记录每个课程的依赖者
   * 2. 一个数组，记录结果
   * 3. 一个标记，记录是不是有效
   * 4. 一个 visited 数组，表示位置被访问过了：0 未 1 正在 2 已
   */
  static class dfs {
    int[] res;
    int idx;
    // graph 的 from to 意思是：to 依赖 from
    List<List<Integer>> graph = new ArrayList<>();
    int[] visited;
    boolean valid = true;
    public int[] findOrder(int numCourses, int[][] prerequisites) {
      idx = numCourses - 1;
      res = new int[numCourses];
      visited = new int[numCourses];
      for (int i = 0; i < numCourses; i++) {
        graph.add(new ArrayList<>());
      }
      for (int[] pair : prerequisites) {
        graph.get(pair[1]).add(pair[0]);
      }
      System.out.println(graph);
      for (int i = 0; valid && i < numCourses; i++) {
        if (visited[i] == 0) {
          dfs(i);
        }
      }
      if (!valid) {
        return new int[0];
      }
      return res;
    }

    /**
     * dfs 就是从 i 开始，顺着 graph 找
     * 期间 visited 的每个节点都是 1
     * 结束后 visited 是 2
     * 如果遇到 visited 是 1 的节点说明有环，valid 设为 false
     *
     * 比如 1,2 2,3 4,1
     * 第一个返回的是没有依赖的那个，往最后面放，倒着放进 res
     */
    void dfs(int i) {
      // 访问时标记成 1
      visited[i] = 1;
      for (Integer to : graph.get(i)) {
        if (visited[to] == 1) {
          valid = false;
          return;
        }
        if (visited[to] == 0) {
          dfs(to);
          if (!valid) {
            return;
          }
        }
      }
      // 访问后，是 2
      visited[i] = 2;
      res[idx--] = i;
    }
  }

  /**
   * 这个 bfs 其实更接近课程表的传统解法：拓扑排序
   * 需要一个数据记录入度，需要一个队列保存入度为 0 的下标
   *
   * 我以为 bfs 会把图的依赖关系搞成：a: [a 依赖的1，a 依赖的 2...] 其实不是
   * 还是 a: [依赖 a 的1，依赖 a 的 2, ...]
   */
  static class bfs {

    int[] res;
    int[] indegrees;
    int idx;
    Queue<Integer> q = new LinkedList<>();
    List<List<Integer>> graph = new ArrayList<>();
    public int[] findOrder(int numCourses, int[][] prerequisites) {
      res = new int[numCourses];
      indegrees = res.clone();
      for (int i = 0; i < numCourses; i++) {
        graph.add(new ArrayList<>());
      }
      for (int[] each : prerequisites) {
        graph.get(each[1]).add(each[0]);
        indegrees[each[0]]++;
      }
      for (int i = 0; i < indegrees.length; i++) {
        if (indegrees[i] == 0) {
          q.offer(i);
        }
      }
      while (!q.isEmpty()) {
        Integer i = q.poll();
        res[idx++] = i;
        for (Integer j : graph.get(i)) {
          indegrees[j]--;
          if (indegrees[j] == 0) {
            q.offer(j);
          }
        }
      }
      if (numCourses != idx) {
        return new int[0];
      }
      return res;
    }
  }

  public static void main(String[] args) {
    // numCourses = 4, prerequisites = [[1,0],[2,0],[3,1],[3,2]]
    // 0 2 1 3
//    int[] res = new bfs().findOrder(4, new int[][]{{1, 0}, {2, 0}, {3, 1}, {3, 2}});
    int[] res = new bfs().findOrder(2, new int[][]{{1, 0}, {0, 1}});
    System.out.println(Arrays.toString(res));
  }
}
